package com.hy.treeNode2;

import com.hy.treeNode.TreeNode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

public class BalanceTreeNode {


    /**
     * 110.平衡二叉树
     * 力扣题目链接
     *
     * 给定一个二叉树，判断它是否是高度平衡的二叉树。
     *
     * 本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
     *
     * 示例 1:
     *
     * 给定二叉树 [3,9,20,null,null,15,7]
     *
     * 本题思路
     * 递归
     * 此时大家应该明白了既然要求比较高度，必然是要后序遍历。
     *
     * 递归三步曲分析：
     *
     * 明确递归函数的参数和返回值
     * 参数：当前传入节点。
     * 返回值：以当前传入节点为根节点的树的高度。
     *
     * 那么如何标记左右子树是否差值大于1呢？
     *
     * 如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，还返回高度的话就没有意义了。
     *
     * 所以如果已经不是二叉平衡树了，可以返回-1 来标记已经不符合平衡树的规则了。
     *
     *
     */

    public boolean isBalancedTreeNode2(TreeNode root){
        return getHeight(root) != -1 ? true : false;
    }
    /**
     * 递归法
     * @param root
     * @return
     */
    public int getHeight(TreeNode root){
        if (root == null){
            return 0;
        }
        int leftHeight = getTreeHeight(root.left);
        if (leftHeight == -1){
            return -1;
        }

        int rightHeight = getTreeHeight(root.right);
        if (rightHeight == -1){
            return -1;
        }
        // math.abs 绝对值  左右子树高度差大于1，return -1表示已经不是平衡树了
        if (Math.abs(leftHeight - rightHeight) > 1){
            return -1;
        }
         // 加上 root 节点
        return Math.max(leftHeight,rightHeight) + 1;
    }

    /**
     * 迭代法，效率较低，计算高度时会重复遍历
     * 时间复杂度：O(n^2)
     * @param root
     * @return
     */
    public boolean isBalancedTreeNode(TreeNode root){
        if (root == null){
            return true;
        }
        Stack<TreeNode> st = new Stack<>();
        TreeNode pre = null;
        while (root != null || !st.isEmpty()){
            if (root != null){
                st.push(root);
                root = root.left;
            }
            // 相当于  root
            TreeNode inNode = st.peek();
            // 右结点为null或已经遍历过
            if (inNode.right == null || inNode.right == pre){
                // 比较左右子树的高度差，输出
                if (Math.abs(getTreeHeight(inNode.left) - getTreeHeight(inNode.right)) > 1){
                    return false;
                }
                st.pop();
                pre = inNode;
                // 当前结点下，没有要遍历的结点了
                root = null;
            }else {
                // 右结点还没遍历，遍历右结点
                root = inNode.right;
            }
        }
        return true;
    }

    /**
     * 层序遍历  获取二叉树的高度
     * @param root
     * @return
     */
    public int getTreeHeight(TreeNode root){
        Deque<TreeNode> deque = new LinkedList<>();
        if (root == null){
            return 0;
        }
        deque.offerLast(root);
        int depth = 0;
        while (!deque.isEmpty()){
            int len = deque.size();
            depth++;
            for (int i = 0; i < len; i++) {
                TreeNode node = deque.pollFirst();
                if (node.left != null){
                    deque.offerLast(node.left);
                }
                if (node.right != null){
                    deque.offerLast(node.right);
                }
            }
        }
        return depth;
    }



    public static void main(String[] args) {
        TreeNode leftNode3 = new TreeNode(8, null, null);
        TreeNode rightNode3 = new TreeNode(8, null, null);

        TreeNode leftNode2 = new TreeNode(4, null, null);
        TreeNode rightNode2 = new TreeNode(3, null, rightNode3);

        TreeNode leftNode1 = new TreeNode(3, leftNode3, null);
        TreeNode rightNode1 = new TreeNode(4, null, null);

        TreeNode leftNode = new TreeNode(2, leftNode1, leftNode1);
        TreeNode rightNode = new TreeNode(2, leftNode2, rightNode2);

        TreeNode root = new TreeNode(1, leftNode, rightNode);

        BalanceTreeNode balanceTreeNode = new BalanceTreeNode();
        System.out.println("是否是高度平衡的二叉树(层序遍历): "+balanceTreeNode.isBalancedTreeNode(root));
        System.out.println("是否是高度平衡的二叉树(递归): "+balanceTreeNode.isBalancedTreeNode2(root));


    }
}
